package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href="https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/">两个链表的第一个公共结点</a>
 * <p>
 * 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
 * </p>
 *
 * @author c2b
 * @since 2023/3/7 15:43
 */
public class JzOffer0052GetIntersectionNode_S {


    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempListA = headA;
        ListNode tempListB = headB;
        // 计算链表A和链表B的长度差值
        int diffCount = 0;
        while (tempListA != null) {
            ++diffCount;
            tempListA = tempListA.next;
        }
        while (tempListB != null) {
            --diffCount;
            tempListB = tempListB.next;
        }
        tempListA = headA;
        tempListB = headB;
        if (diffCount > 0) {
            // A链表较长，A先走差值步
            for (int i = 0; i < diffCount; ++i) {
                tempListA = tempListA.next;
            }
        } else {
            // B链表较长，B先走差值步
            for (int i = 0; i > diffCount; --i) {
                tempListB = tempListB.next;
            }
        }
        while (tempListA != null) {
            if (tempListA == tempListB) {
                return tempListA;
            }
            tempListA = tempListA.next;
            tempListB = tempListB.next;
        }
        return null;
    }


    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        int diff = 0;
        ListNode temp1 = pHead1;
        ListNode temp2 = pHead2;
        while (temp1 != null) {
            diff++;
            temp1 = temp1.next;
        }
        while (temp2 != null) {
            diff--;
            temp2 = temp2.next;
        }
        if (diff >= 0) {
            // 这种情况说明链表1的长度大于等于链表2的长度，链表1先走差值步
            for (int i = 0; i < diff; i++) {
                pHead1 = pHead1.next;
            }
        } else {
            // 这种情况说明链表2的长度大于等于链表1的长度，链表2先走差值步
            for (int i = 0; i > diff; i--) {
                pHead2 = pHead2.next;
            }
        }
        // 此时链表1 和 链表2 同时遍历
        while (pHead1 != null) {
            if (pHead1.val == pHead2.val) {
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode pHead1 = new ListNode(1);
        pHead1.next = new ListNode(2);
        pHead1.next.next = new ListNode(3);
        pHead1.next.next.next = new ListNode(6);
        pHead1.next.next.next.next = new ListNode(7);
        ListNode pHead2 = new ListNode(4);
        pHead2.next = new ListNode(5);
        pHead2.next.next = pHead1.next.next.next;
        pHead2.next.next.next = pHead1.next.next.next.next;
        JzOffer0052GetIntersectionNode_S jzOffer0052FindFirstCommonNode = new JzOffer0052GetIntersectionNode_S();
        ListNode listNode = jzOffer0052FindFirstCommonNode.getIntersectionNode(pHead2, pHead1);
        System.out.println();
    }
}
